#include "BinaryTree.h"

TreeNode* createNode(ElemType data) {
    TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

TreeNode* createNodeWithChildren(ElemType data, TreeNode* left,
                                 TreeNode* right) {
    TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
    new_node->data = data;
    new_node->left = left;
    new_node->right = right;
    return new_node;
}

int isEmpty(TreeNode* root) { return root == NULL; }

int isLeaf(TreeNode* root) {
    return root == NULL ? -1 : root->left == NULL && root->right == NULL;
}

int height(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int left_height = height(root->left);
    int right_height = height(root->right);
    return 1 + (left_height > right_height ? left_height : right_height);
}

ElemType get(TreeNode* root) {
    if (root == NULL) {
        printf("get: Tree is empty.\n");
        return -1;
    }
    return root->data;
}

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

// 输出重定向到数组
void preOrderToArray(TreeNode* root, ElemType* arr, int* retSize) {
    if (root == NULL) {
        return;
    }
    arr[(*retSize)++] = root->data;
    preOrderToArray(root->left, arr, retSize);
    preOrderToArray(root->right, arr, retSize);
}

void preOrderNor(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = init_stack();
    TreeNode* cur = root;
    while (cur != NULL || !is_empty_stack(stack)) {
        while (cur != NULL) {
            printf("%d ", cur->data);
            push(stack, cur);
            cur = cur->left;
        }
        cur = pop(stack);
        cur = cur->right;
    }
    free(stack);
}

void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

void inOrderNor(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = init_stack();
    TreeNode* cur = root;
    while (cur != NULL || !is_empty_stack(stack)) {
        while (cur != NULL) {
            push(stack, cur);
            cur = cur->left;
        }
        cur = pop(stack);
        printf("%d ", cur->data);
        cur = cur->right;
    }
    free(stack);
}

void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

void postOrderNor(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = init_stack();
    TreeNode* cur = root;
    TreeNode* visited = NULL;
    while (cur != NULL || !is_empty_stack(stack)) {
        while (cur != NULL) {
            push(stack, cur);
            cur = cur->left;
        }
        TreeNode* top = peek(stack);
        // cur = peek(stack);
        if (top->right == NULL || top->right == visited) {
            printf("%d ", top->data);
            pop(stack);
            visited = top;
        } else {
            cur = top->right;
        }
    }
    free(stack);
}

void levelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Queue* queue = init_queue();
    enqueue(queue, root);
    while (!is_empty_queue(queue)) {
        TreeNode* cur = dequeue(queue);
        printf("%d ", cur->data);
        if (cur->left != NULL) {
            enqueue(queue, cur->left);
        }
        if (cur->right != NULL) {
            enqueue(queue, cur->right);
        }
    }
    free(queue);
}

void show(void (*order)(TreeNode*), TreeNode* root) {
    printf("[ ");
    order(root);
    printf("]\n");
}

int count(TreeNode* root) {
    return isEmpty(root) ? 0 : 1 + count(root->left) + count(root->right);
}

int countOfKLevel(TreeNode* root, int k) {
    return root == NULL || k <= 0 ? 0  // 空树或非法输入直接返回0
           : k == 1               ? 1  // 第1层只有一个节点，返回1
                                       // 递归计算第k层的节点数
                    : countOfKLevel(root->left, k - 1) +
                          // 递归计算第k层的节点数
                          countOfKLevel(root->right, k - 1);
}

void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}
